package offer

/*
时间复杂度:O(n+m) 对图进行广度优先搜索的时间复杂度(每个节点和每条边都各访问一遍)
空间复杂度:O(n+m) 邻接表(存储每个节点和每条边,edges的第一维存储的是N个节点,edges[i]存储的是与节点i相邻的有向边,所以第二维存储的是所有的边)

f1:拓扑排序
*/

func findOrder(numCourses int, prerequisites [][]int) []int {
	var (
		// 构建邻接表
		edges = make([][]int, numCourses)
		// 记录拓扑排序结果
		result []int
		// 入度表
		inDegree = make([]int, numCourses)
		// 存储入度为0的节点
		queue []int
	)

	for _, info := range prerequisites {
		edges[info[1]] = append(edges[info[1]], info[0])
		inDegree[info[0]]++
	}

	for i, v := range inDegree {
		if v == 0 {
			queue = append(queue, i)
		}
	}

	for len(queue) != 0 {
		e := queue[0]
		queue = queue[1:]
		result = append(result, e)
		for _, v := range edges[e] {
			inDegree[v]--
			if inDegree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	if len(result) == numCourses {
		return result
	}
	return []int{}
}

/*
时间复杂度:O(n+m) 对图进行广度优先搜索的时间复杂度(每个节点和每条边都各访问一遍)
空间复杂度:O(n+m) 邻接表(存储每个节点和每条边,edges的第一维存储的是N个节点,edges[i]存储的是与节点i相邻的有向边,所以第二维存储的是所有的边)

f2:dfs
*/

func findOrder1(numCourses int, prerequisites [][]int) []int {
	var (
		edges = make([][]int, numCourses)
		dfs   func(u int)
		// 节点是否访问过,0表示未访问,1表示正在访问,2表示已访问
		visited = make([]int, numCourses)
		valid   = true
		result  []int
	)

	dfs = func(u int) {
		// 将节点设置为1,表示正在访问
		visited[u] = 1
		// 遍历节点u的相邻节点
		for _, v := range edges[u] {
			if visited[v] == 0 {
				dfs(v)
				if !valid {
					return
				}
			} else if visited[v] == 1 {
				// 在dfs过程中遇到了正在访问的元素,说明有环,无法构成拓扑排序
				valid = false
				return
			}
		}
		// 表示节点访问完毕
		visited[u] = 2
		result = append(result, u)
	}

	for _, info := range prerequisites {
		edges[info[1]] = append(edges[info[1]], info[0])
	}

	for i := 0; i < numCourses; i++ {
		if visited[i] == 0 && valid {
			dfs(i)
		}
	}
	if !valid {
		return []int{}
	}
	return reverse(result)
}

func reverse(arr []int) []int {
	for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
		arr[i], arr[j] = arr[j], arr[i]
	}
	return arr
}
